home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / documents / RFC / rfc1075.txt < prev    next >
Text File  |  1994-08-01  |  53KB  |  1,347 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                        D. Waitzman
  8. Request For Comments: 1075                                  C. Partridge
  9.                                                                  BBN STC
  10.                                                               S. Deering
  11.                                                      Stanford University
  12.                                                            November 1988
  13.  
  14.                Distance Vector Multicast Routing Protocol
  15.  
  16. 1. Status of this Memo
  17.  
  18.    This RFC describes a distance-vector-style routing protocol for
  19.    routing multicast datagrams through an internet.  It is derived from
  20.    the Routing Information Protocol (RIP) [1], and implements
  21.    multicasting as described in RFC-1054.  This is an experimental
  22.    protocol, and its implementation is not recommended at this time.
  23.    Distribution of this memo is unlimited.
  24.  
  25. 2. Introduction
  26.  
  27.    A draft standard for multicasting over IP networks now exists [2],
  28.    but no routing protocols to support internetwork multicasting are
  29.    available.  This memo describes an experimental routing protocol,
  30.    named DVMRP, that implements internetwork multicasting.  DVMRP
  31.    combines many of the features of RIP [1] with the Truncated Reverse
  32.    Path Broadcasting (TRPB) algorithm described by Deering [3].
  33.  
  34.    DVMRP is an "interior gateway protocol"; suitable for use within an
  35.    autonomous system, but not between different autonomous systems.
  36.    DVMRP is not currently developed for use in routing non-multicast
  37.    datagrams, so a router that routes both multicast and unicast
  38.    datagrams must run two separate routing processes.  DVMRP is designed
  39.    to be easily extensible and could be extended to route unicast
  40.    datagrams.
  41.  
  42.    DVMRP was developed to experiment with the algorithms in [3].  RIP
  43.    was used as the starting point for the development because an
  44.    implementation was available and distance vector algorithms are
  45.    simple, as compared to link-state algorithms [4].  In addition, to
  46.    allow experiments to traverse networks that do not support
  47.    multicasting, a mechanism called "tunneling" was developed.
  48.  
  49.    The multicast forwarding algorithm requires the building of trees
  50.    based on routing information.  This tree building needs more state
  51.    information than RIP is designed to provide, so DVMRP is much more
  52.    complicated in some places than RIP.  A link-state algorithm, which
  53.    already maintains much of the state needed, might prove a better
  54.    basis for Internet multicasting routing and forwarding.
  55.  
  56.  
  57.  
  58. Waitzman, Partridge & Deering                                   [Page 1]
  59.  
  60. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  61.  
  62.  
  63.    DVMRP differs from RIP in one very important way.  RIP thinks in
  64.    terms of routing and forwarding datagrams to a particular
  65.    destination.  The purpose of DVMRP is to keep track of the return
  66.    paths to the source of multicast datagrams.  To make explanation of
  67.    DVMRP more consistent with RIP, the word "destination" is used
  68.    instead of the more proper "source", but the reader must remember
  69.    that datagrams are not forwarded to these destinations, but originate
  70.    from them.
  71.  
  72.    This memo is organized into the following sections:
  73.            - A description of DVMRP is presented.
  74.            - Tunnels are explained.
  75.            - The routing algorithm is shown.
  76.            - The forwarding algorithm is shown.
  77.            - The various time values are listed.
  78.            - Configuration information is specified.
  79.  
  80.    This memo does not analyze distance-vector routing, nor fully explain
  81.    the distance-vector algorithm; see [1] for more information on these
  82.    topics.  The process or processes that perform the routing and
  83.    forwarding functions are called "routers" in this memo.
  84.  
  85. 3. Protocol Description
  86.  
  87.    DVMRP uses the Internet Group Management Protocol (IGMP) to exchange
  88.    routing datagrams [2].
  89.  
  90.    DVMRP datagrams are composed of two portions: a small, fixed length
  91.    IGMP header, and a stream of tagged data.
  92.  
  93.    The fixed length IGMP header of DVMRP messages is:
  94.  
  95.        0                   1                   2                   3
  96.        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  97.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  98.       |Version| Type  |  Subtype      |           Checksum            |
  99.       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  100.  
  101.    The version is 1.
  102.  
  103.    The type for DVMRP is 3.
  104.  
  105.    The subtype is one of:
  106.  
  107.    1 = Response; the message provides routes to some destination(s).
  108.    2 = Request; the message requests routes to some destination(s).
  109.    3 = Non-membership report; the message provides non-membership
  110.        report(s).
  111.  
  112.  
  113.  
  114. Waitzman, Partridge & Deering                                   [Page 2]
  115.  
  116. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  117.  
  118.  
  119.    4 = Non-membership cancellation; the message cancels previous
  120.        non-membership report(s).
  121.  
  122.    The checksum is the 16-bit one's complement of the one's complement
  123.    sum of the entire message, excluding the IP header.  For computing
  124.    the checksum, the checksum field is zeroed.
  125.  
  126.    The rest of the DVMRP message is a stream of tagged data.  The reason
  127.    for using a stream of tagged data is to provide easy extensibility
  128.    (new commands can be developed by adding new tags) and to reduce the
  129.    amount of redundant data in a message.  The elements in the stream,
  130.    called commands, are multiples of 16 bits, for convenient alignment.
  131.    The commands are organized as an eight bit command numeric code, with
  132.    at least an eight bit data portion.  Sixteen-bit alignment of all
  133.    commands is required.
  134.  
  135.    A message that has an error in it will be discarded at the point in
  136.    processing where the error is detected.  Any state changed due to the
  137.    message contents before the error will not be restored to its
  138.    previous values.
  139.  
  140.    Certain commands have default values defined in their specification.
  141.    As the defaults may be changed as the protocol is developed further,
  142.    a cautious implementation will not send out messages that depend on
  143.    defaults.
  144.  
  145.    The length of DVMRP messages is limited to 512 bytes, excluding the
  146.    IP header.
  147.  
  148. 3.1 NULL Command
  149.  
  150.    Format:  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
  151.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  152.            |        0      |  |    Ignored    |
  153.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  154.  
  155.    Description: The NULL command can be used to provide additional
  156.    alignment or padding to 32 bits.
  157.  
  158. 3.2 Address Family Indicator (AFI) Command
  159.  
  160.    Format:  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
  161.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  162.            |        2      |  |     family    |
  163.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170. Waitzman, Partridge & Deering                                   [Page 3]
  171.  
  172. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  173.  
  174.  
  175.    Values for family:
  176.  
  177.       2 = IP address family, in which addresses are 32 bits long.
  178.  
  179.    Default: Family = 2.
  180.  
  181.    Description: The AFI command provides the address family for
  182.    subsequent addresses in the stream (until a different AFI command is
  183.    given).
  184.  
  185.    It is an error if the receiver does not support the address family.
  186.  
  187. 3.3 Subnetmask Command
  188.  
  189.    Format:  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
  190.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  191.            |        3      |  |     count     |
  192.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  193.  
  194.    Additional argument, with AFI = IP:
  195.  
  196.     0                   1                   2                   3
  197.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  198.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  199.    | Subnet mask                                                   |
  200.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  201.  
  202.    Count is 0 or 1.
  203.  
  204.    Default: Assume that following routes are to networks, and use a mask
  205.    of the network mask of each route's destination.
  206.  
  207.    Description: The Subnetmask command provides the subnet mask to use
  208.    for subsequent routes.  There are some requirements on the bits in
  209.    the subnetmask: bits 0 through 7 must be 1, and all of the bits must
  210.    not be 1.
  211.  
  212.    If the count is 0, then no subnet mask applies, assume that the
  213.    following routes are to networks, and use a mask of the network mask
  214.    of each route's destination.  If count is 1, then a subnet mask
  215.    should be in the data stream, of an appropriate size given the
  216.    address family.
  217.  
  218.    It is an error for count not to equal 0 or 1.
  219.  
  220.    Subnetmasks should not be sent outside of the appropriate network.
  221.  
  222.    See [6] for more information regarding IP subnetting.
  223.  
  224.  
  225.  
  226. Waitzman, Partridge & Deering                                   [Page 4]
  227.  
  228. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  229.  
  230.  
  231. 3.4 Metric Command
  232.  
  233.    Format:  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
  234.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  235.            |        4      |  |     value     |
  236.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  237.  
  238.    Value is the metric, as an unsigned value ranging from 1 to 255.
  239.  
  240.    Default: None.
  241.  
  242.    Description: The metric command provides the metric to subsequent
  243.    destinations.  The metric is relative to the router that sent this
  244.    DVMRP routing update.
  245.  
  246.    It is an error for metric to equal 0.
  247.  
  248. 3.5 Flags0 Command
  249.  
  250.    Format:  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
  251.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  252.            |        5      |  |     value     |
  253.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  254.  
  255.    Meaning of bits in value:
  256.  
  257.       Bit 7: Destination is unreachable.
  258.       Bit 6: Split Horizon concealed route.
  259.  
  260.    Default: All bits zero.
  261.  
  262.    Description: The flags0 command provides a way to set a number of
  263.    flags.  The only defined flags, bits 6 and 7, can be used to provide
  264.    more information about a route with a metric of infinity.  A router
  265.    that receives a flag that it does not support should ignore the flag.
  266.    The command is called flags0 to permit the definition of additional
  267.    flag commands in the future (flags1, etc.).
  268.  
  269.    This is an experimental command, and may be changed in the future.
  270.  
  271. 3.6 Infinity Command
  272.  
  273.    Format:  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
  274.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  275.            |        6      |  |     value     |
  276.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  277.  
  278.    Value is the infinity, as an unsigned value ranging from 1 to 255.
  279.  
  280.  
  281.  
  282. Waitzman, Partridge & Deering                                   [Page 5]
  283.  
  284. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  285.  
  286.  
  287.    Default: Value = 16.
  288.  
  289.    Description: The infinity command defines the infinity for subsequent
  290.    metrics in the stream.
  291.  
  292.    It is an error for infinity to be zero, or less than the current
  293.    metric.
  294.  
  295. 3.7 Destination Address (DA) Command
  296.  
  297.    Format:  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
  298.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  299.            |        7      |  |     count     |
  300.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  301.  
  302.    Array of 'count' additional arguments, with AFI = IP:
  303.  
  304.     0                   1                   2                   3
  305.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  306.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  307.    | Destination Address1                                          |
  308.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  309.  
  310.     0                   1                   2                   3
  311.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  312.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  313.    | Destination Address2                                          |
  314.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  315.  
  316.    Count is the number of addresses supplied, from 1 to 255.  The length
  317.    of the addresses depends upon the current address family.  The number
  318.    of addresses supplied is subject to the message length limitation of
  319.    512 bytes.
  320.  
  321.    Default: None.
  322.  
  323.    Description: The DA command provides a list of destinations.  While
  324.    this format can express routes to hosts, the routing algorithm only
  325.    supports network and subnetwork routing.  The current metric,
  326.    infinity, flags0 and subnetmask, when combined with a single
  327.    destination address, define a route.  The current metric must be less
  328.    than or equal to the current infinity.
  329.  
  330.    It is an error for count to equal 0.
  331.  
  332.  
  333.  
  334.  
  335.  
  336.  
  337.  
  338. Waitzman, Partridge & Deering                                   [Page 6]
  339.  
  340. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  341.  
  342.  
  343. 3.8 Requested Destination Address (RDA) Command
  344.  
  345.    Format:  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
  346.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  347.            |        8      |  |     count     |
  348.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  349.  
  350.    Array of 'count' additional arguments, with AFI = IP:
  351.  
  352.     0                   1                   2                   3
  353.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  354.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  355.    | Requested Destination Address1                                |
  356.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  357.  
  358.     0                   1                   2                   3
  359.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  360.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  361.    | Requested Destination Address2                                |
  362.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  363.  
  364.    Count is the number of addresses supplied, from 0 to 255.  The length
  365.    of the addresses depends upon the current address family.  The number
  366.    of addresses supplied is subject to the message length limitation of
  367.    512 bytes.
  368.  
  369.    Default: None.
  370.  
  371.    Description: The RDA command provides a list of destinations for whom
  372.    routes are requested.  A routing request for all routes is encoded by
  373.    using a count = 0.
  374.  
  375. 3.9 Non Membership Report (NMR) Command
  376.  
  377.    Format:  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
  378.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  379.            |        9      |  |     count     |
  380.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  381.  
  382.     Array of 'count' additional arguments, with AFI = IP:
  383.  
  384.     0                   1                   2                   3
  385.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  386.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  387.    | Multicast Address1                                            |
  388.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  389.  
  390.  
  391.  
  392.  
  393.  
  394. Waitzman, Partridge & Deering                                   [Page 7]
  395.  
  396. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  397.  
  398.  
  399.     0                   1                   2                   3
  400.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  401.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  402.    | Hold Down Time1                                               |
  403.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  404.  
  405.     0                   1                   2                   3
  406.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  407.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  408.    | Multicast Address2                                            |
  409.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  410.  
  411.     0                   1                   2                   3
  412.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  413.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  414.    | Hold Down Time2                                               |
  415.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  416.  
  417.    Count is the number of Multicast Address and Hold Down Time pairs
  418.    supplied, from 1 to 255.  The length of the addresses depends upon
  419.    the current address family.  The number of pairs supplied is subject
  420.    to the message length limitation of 512 bytes.
  421.  
  422.    Default: None.
  423.  
  424.    Description: The NMR command is experimental, and has not been tested
  425.    in an implementation.  Each multicast address and hold down time pair
  426.    is called a non-membership report.  The non-membership report tells
  427.    the receiving router that the sending router has no descendent group
  428.    members in the given group.  Based on this information the receiving
  429.    router can stop forwarding datagrams to the sending router for the
  430.    particular multicast address(es) listed.  The hold down time
  431.    indicates, in seconds, how long the NMR is valid.
  432.  
  433.    It is an error for count to equal 0.
  434.  
  435.    The only other commands in a message that has NMR commands can be the
  436.    AFI, flags0, and NULL commands.  No relevant flags for the flags0
  437.    command are currently defined, but that may change in the future.
  438.  
  439. 3.10 Non Membership Report Cancel (NMR Cancel) Command
  440.  
  441.    Format:  0 1 2 3 4 5 6 7    0 1 2 3 4 5 6 7
  442.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  443.            |       10      |  |     count     |
  444.            +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Waitzman, Partridge & Deering                                   [Page 8]
  451.  
  452. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  453.  
  454.  
  455.     Array of 'count' additional arguments, with AFI = IP:
  456.  
  457.     0                   1                   2                   3
  458.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  459.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  460.    | Multicast Address1                                            |
  461.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  462.  
  463.     0                   1                   2                   3
  464.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  465.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  466.    | Multicast Address2                                            |
  467.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  468.  
  469.    Count is the number of Multicast Addresses supplied, from 1 to 255.
  470.    The length of the addresses depends upon the current address family.
  471.    The number of addresses supplied is subject to the message length
  472.    limitation of 512 bytes.
  473.  
  474.    Default: None.
  475.  
  476.    Description: The NMR Cancel command is experimental, and has not been
  477.    tested in an implementation.  For each multicast address listed, any
  478.    previous corresponding non-membership reports are canceled.  When
  479.    there is no corresponding non-membership report for a given multicast
  480.    address, the Cancel command should be ignored for that multicast
  481.    address.
  482.  
  483.    It is an error for count to equal 0.
  484.  
  485.    The only other commands in a message that has NMR Cancel commands can
  486.    be the AFI, flags0, and NULL commands.  No relevant flags for the
  487.    flags0 command are currently defined, but that may change in the
  488.    future.
  489.  
  490. 3.12 Examples (with bytes in '{}'), not including the message header:
  491.  
  492. 3.12.1 Supplying a single route to the IP address 128.2.251.231 with
  493.    a metric of 2, an infinity of 16, a subnetmask of 255.255.255.0:
  494.  
  495.    Subtype 1,
  496.    AFI 2,  Metric 2, Infinity 16, Subnet Mask 255.255.255.0
  497.    {2} {2} {4} {2}   {6} {16}     {3} {1} {255} {255} {255} {0}
  498.  
  499.    DA Count=1 [128.2.251.231]
  500.    {7} {1} {128} {2} {251} {231}
  501.  
  502.  
  503.  
  504.  
  505.  
  506. Waitzman, Partridge & Deering                                   [Page 9]
  507.  
  508. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  509.  
  510.  
  511. 3.12.2 Supplying a route to the IP addresses 128.2.251.231 and
  512.    128.2.236.2 with a metric of 2, an infinity of 16, a subnetmask of
  513.    255.255.255.0:
  514.  
  515.    Subtype 1,
  516.    AFI 2,  Metric 2, Infinity 16, Subnet Mask 255.255.255.0
  517.    {2} {2} {4} {2}   {6} {16}     {3} {1} 255} {255} {255} {0}
  518.  
  519.    DA Count=2 [128.2.251.231] [128.2.236.2]
  520.    {7} {1} {128} {2} {251} {231} {128} {2} {236} {2}
  521.  
  522. 3.12.3 Request for all routes to IP destinations.
  523.  
  524.    Subtype 2, AFI 2,  RDA Count = 0
  525.               {2} {2} {8} {0}
  526.  
  527. 3.12.4 Non Membership Report for groups 224.2.3.1 and 224.5.4.6 with a
  528.    hold down time of 20 seconds, and group 224.7.8.5 with a hold down
  529.    time of 40 seconds.
  530.  
  531.    Subtype 3,
  532.    AFI 2,  NMR Count = 3 [224.2.3.1, 20]
  533.    {2} {2} {10} {3} {224} {2} {3} {1} {0} {0} {0} {20}
  534.  
  535.    [224.5.4.6, 20] [224.7.8.5, 40]
  536.    {224} {5} {4} {6} {0} {0} {0} {20} {224} {7} {8} {5} {0} {0} {0} {40}
  537.  
  538. 3.13 Summary of Commands
  539.  
  540.  
  541.    Value   Name            Other commands allowed in same message
  542.    -----   ----            ---------------------------------------
  543.    0       Null            Null, AFI, Subnetmask, Metric, Flags0,
  544.                            Infinity, DA, RDA, NMR, NMR-cancel
  545.  
  546.    2       AFI             Null, AFI, Subnetmask, Metric, Flags0,
  547.                            Infinity, DA, RDA, NMR, NMR-cancel
  548.  
  549.    3       Subnetmask      Null, AFI, Subnetmask, Metric, Flags0,
  550.                            Infinity, DA, RDA
  551.  
  552.    4       Metric          Null, AFI, Subnetmask, Metric, Flags0,
  553.                            Infinity, DA
  554.  
  555.    5       Flags0          Null, AFI, Subnetmask, Metric, Flags0,
  556.                            Infinity, DA
  557.  
  558.  
  559.  
  560.  
  561.  
  562. Waitzman, Partridge & Deering                                  [Page 10]
  563.  
  564. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  565.  
  566.  
  567.    6       Infinity        Null, AFI, Subnetmask, Metric, Flags0,
  568.                            Infinity, DA
  569.  
  570.    7       DA              Null, AFI, Subnetmask, Metric, Flags0,
  571.                            Infinity, DA
  572.  
  573.    8       RDA             Null, AFI, Subnetmask, Flags0, RDA
  574.  
  575.    9       NMR             Null, AFI, Flags0, NMR
  576.  
  577.    10      NMR-cancel      Null, AFI, Flags0, NMR-cancel
  578.  
  579.  
  580. 4. Tunnels
  581.  
  582.    A tunnel is a method for sending datagrams between routers separated
  583.    by gateways that do not support multicasting routing.  It acts as a
  584.    virtual network between two routers.  For instance, a router running
  585.    at Stanford, and a router running at BBN might be connected with a
  586.    tunnel to allow multicast datagrams to traverse the Internet.  We
  587.    consider tunnels to be a transitional hack.
  588.  
  589.    Tunneling is done with a weakly encapsulated normal multicasted
  590.    datagram.  The weak encapsulation uses a special two element IP loose
  591.    source route [5].  (This form of encapsulation is preferable to
  592.    "strong" encapsulation, i.e., prepending an entire new IP header,
  593.    because it does not require the tunnel end-points to know each
  594.    other's maximum reassembly buffer size.  It also has the benefit of
  595.    correct behavior of the originator's time-to-live value and any other
  596.    IP options present.)
  597.  
  598.    A tunnel has a local end-point, remote end-point, metric, and
  599.    threshold associated with it.  The routers at each end of the tunnel
  600.    need only agree upon the local and remote end-points.  See section 8
  601.    for information on how tunnels are configured.  Because the number of
  602.    intermediate gateways between the end-points of a tunnel is unknown,
  603.    additional research is needed to determine appropriate metrics and
  604.    thresholds.
  605.  
  606.    To send a datagram on a tunnel, the following occurs:
  607.  
  608.       - A null IP option is inserted into the datagram.  This provides
  609.         preferred alignment for the loose source route IP option.
  610.  
  611.       - A two element loose source route IP option is inserted into
  612.         the datagram.
  613.  
  614.       - The source route pointer is set to point to the second element
  615.  
  616.  
  617.  
  618. Waitzman, Partridge & Deering                                  [Page 11]
  619.  
  620. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  621.  
  622.  
  623.         in the source route.
  624.  
  625.       - The first element in the source route is replaced with the
  626.         address of the originating host (the original IP source
  627.         address).
  628.  
  629.       - The second element in the source route is replaced with the
  630.         multicast destination address provided by the originating host
  631.         (the original IP destination address).
  632.  
  633.       - The IP source address is replaced with the address of the
  634.         router's appropriate outgoing physical interface (the local
  635.         tunnel end-point).
  636.  
  637.       - The IP destination address is replaced with an address of the
  638.         remote router (the remote tunnel end-point).
  639.  
  640.       - The datagram is transmitted to the remote router using
  641.         non-multicast routing algorithms.
  642.  
  643.    Intermediate, non-multicast gateways will route the tunneled datagram
  644.    to the remote tunnel end-point.  Because the datagram's IP source
  645.    address has been replaced with the address of the local tunnel end-
  646.    point, ICMP error messages will go to the originating multicast
  647.    router.  This behavior is desired, because a host that sends a
  648.    multicast datagram, which a multicast router decides to tunnel,
  649.    should not be aware of the use of the tunnel.  If the datagram's IP
  650.    source address were not changed when encapsulating the datagram, any
  651.    ICMP errors would be sent to the originating host.
  652.  
  653.    When the remote tunnel end-point receives the tunneled datagram, the
  654.    following occurs:
  655.  
  656.       - The IP source address is replaced with the first element in the
  657.         loose source route.
  658.  
  659.       - The IP destination address is replaced with the second element
  660.         in the loose source route.
  661.  
  662.       - The null option and the loose source route option are removed
  663.         from the datagram.  This is needed because a host should not
  664.         be able to tell that it has received a datagram that was sent
  665.         through a tunnel.
  666.  
  667.    Because no specific network is associated with a tunnel, there are no
  668.    local group memberships to be tracked for a tunnel.  The only
  669.    neighbor on a tunnel can be the remote end-point.  Routing messages
  670.    should be exchanged through tunnels, but a route is not created for a
  671.  
  672.  
  673.  
  674. Waitzman, Partridge & Deering                                  [Page 12]
  675.  
  676. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  677.  
  678.  
  679.    tunnel.  The routing messages should be sent as unicast datagrams
  680.    directly to the remote tunnel end-point; they should not use an IP
  681.    loose source route.
  682.  
  683.    Justification for using the loose source route and record option for
  684.    tunneling:
  685.  
  686.       We considered defining our own IP option to handle tunneling, but
  687.       we are worried that intermediate gateways do not transparently
  688.       pass IP options that are unknown to them.  Datagrams using a new
  689.       option would not traverse the Internet.  It would be better for us
  690.       if we could create a new IP option, but it won't work presently.
  691.       Recall that this is a transition design to allow us to experiment
  692.       in the current environment.
  693.  
  694.       The tunneled packet containing the LSRR option has the following
  695.       features:
  696.  
  697.                       Field            Value
  698.                       -----            --------------------
  699.                       src address    = src gateway address
  700.                       dst address    = dst gateway address
  701.                       LSRR pointer   = points to LSRR address 2
  702.                       LSRR address 1 = src host
  703.                       LSRR address 2 = multicast destination
  704.  
  705.       Two questions raised about using the LSRR option for tunnels are
  706.       "Can intermediate gateways ignore the option?", and "Can the
  707.       destination gateway properly detect that the LSRR is used for a
  708.       tunnel?".
  709.  
  710.       When an intermediate gateway receives a datagram, it examines the
  711.       destination address.  For a tunneled datagram, the destination
  712.       address will not match an address of the receiving gateway.
  713.       Therefore, the LSRR option will not be examined, and the
  714.       intermediate gateway will forward the datagram on to its next hop
  715.       for the destination address.
  716.  
  717.       When the destination gateway receives a datagram, it notes that
  718.       the datagram destination address matches one of its own address.
  719.       It will then look at the next LSRR option address, since the
  720.       source route is not exhausted.  That address is a multicast
  721.       address.  Since hosts are forbidden from putting multicast
  722.       addresses into source routes, the gateway can infer that the LSRR
  723.       is for tunneling.  The weakness here is that perhaps there is some
  724.       other meaning for the multicast address in the LSRR.  No other
  725.       meaning is currently defined.
  726.  
  727.  
  728.  
  729.  
  730. Waitzman, Partridge & Deering                                  [Page 13]
  731.  
  732. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  733.  
  734.  
  735.       If a tunneled datagram is by error addressed to a destination
  736.       gateway that does not support multicasting, then the destination
  737.       gateway will try to find a route to the multicast address.  This
  738.       will fail, and an ICMP destination unreachable error message will
  739.       be sent to the tunneled datagram's source.  Since the source
  740.       address in the tunneled datagram has been adjusted to be the
  741.       address of the source multicast gateway, the ICMP errors will not
  742.       go to the originating host, which has no knowledge of tunnels.
  743.  
  744. 5. Routing Algorithm
  745.  
  746.    This section provides a terse description of the distance-vector
  747.    routing algorithm.  See [1] for more information.
  748.  
  749.    While DVMRP can express routes to individual hosts, the forwarding
  750.    and routing algorithms only support network and subnetwork routing.
  751.  
  752.    In the discussion below, the term "virtual interface" is used to
  753.    refer to a physical interface or a tunnel local end-point.  A
  754.    physical interface is a network interface, for instance, an Ethernet
  755.    card.  A route to a destination will be through a virtual interface.
  756.    The term "virtual network" is used to refer to a physical network or
  757.    a tunnel, with the qualification that routes only reference physical
  758.    networks.
  759.  
  760.    The TRPB algorithm forwards multicast datagrams by computing the
  761.    shortest (reverse) path tree from the source (physical) network to
  762.    all possible recipients of the datagram.  Each multicast router must
  763.    determine its place in the tree, relative to the particular source,
  764.    and then determine which of its virtual interfaces are in the
  765.    shortest path tree.  The datagram is forwarded out these virtual
  766.    interfaces.  The process of excluding virtual interfaces not in the
  767.    shortest path tree is called "pruning."
  768.  
  769.    Consider a virtual network.  Using Deering's terminology [3], a
  770.    router is called the "parent" of the virtual network if that router
  771.    is responsible for forwarding datagrams onto that virtual network
  772.    through its connecting virtual interface.  The virtual network can
  773.    also be considered a "child" virtual network of the router.  Using
  774.    the child information, routers can do Reverse Path Broadcasting
  775.    (RPB).
  776.  
  777.    Unnecessary datagrams may still be sent onto some networks, because
  778.    there might not be any recipients for those datagrams on the
  779.    networks.  There are two kinds of recipients: hosts that are members
  780.    of a particular multicast group, and multicast routers.  If no
  781.    multicast routers on a virtual network consider that virtual network
  782.    uptree to a given source, then that virtual network is a "leaf"
  783.  
  784.  
  785.  
  786. Waitzman, Partridge & Deering                                  [Page 14]
  787.  
  788. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  789.  
  790.  
  791.    network.  If a network is a leaf for a given source, and there are no
  792.    members of a particular group on the network, then there are no
  793.    recipients for datagrams from the source to the group on that
  794.    network.  That network's parent router can forgo sending those
  795.    datagrams on that network, or "truncate" the shortest path tree.  The
  796.    algorithm that tracks and uses this information is the Truncated
  797.    Reverse Path Broadcasting (TRPB) algorithm.
  798.  
  799.    Determining which virtual networks are leaves is not simple.  If any
  800.    neighboring router considers a given virtual network in the path to a
  801.    given destination, then the virtual network is not a leaf.
  802.    Otherwise, it is a leaf.  This is a voting function.  If a route,
  803.    with a metric poisoned by split horizon processing, is sent by some
  804.    router, then that router uses that virtual network as the uptree path
  805.    for that route (i.e.  that router votes that the virtual network is
  806.    not a leaf relative to the route's destination).  Since the number of
  807.    routers on a virtual network is dynamic, and since all received
  808.    routing updates are not kept by routers, a heuristic is needed to
  809.    determine when a network is a leaf.  DVMRP samples the routing
  810.    updates on a virtual interface while a hold down timer is running,
  811.    which is for a time period of LEAF_TIMEOUT seconds.  There is one
  812.    hold down timer per virtual interface.  If a route is received with a
  813.    metric poisoned by split horizon processing while the hold down timer
  814.    is running, or at any other time, then the appropriate virtual
  815.    interface for that route is "spoiled"-- it is not a leaf.  For every
  816.    route, any virtual interface that was not spoiled by the time the
  817.    hold down timer expires is considered a leaf.
  818.  
  819.    For a description of an even better forwarding algorithm, the Reverse
  820.    Path Multicasting algorithm, see [3].
  821.  
  822.    A route entry should have the following in it:
  823.            - Destination address (a source of multicast datagrams) *
  824.            - Subnet mask of the destination address                *
  825.            - Next-hop router to the destination address
  826.            - Virtual interface to the next-hop router              *
  827.            - List of child virtual interfaces                      *
  828.            - List of leaf virtual interfaces                       *
  829.            - A dominant router address for each virtual interface
  830.            - A subordinate router address for each virtual interface
  831.            - Timer
  832.            - Set of flags that indicate the state of the entry
  833.            - Metric
  834.            - Infinity
  835.  
  836.    The lines that are marked with '*' indicate fields that are directly
  837.    used by the forwarding algorithm.
  838.  
  839.  
  840.  
  841.  
  842. Waitzman, Partridge & Deering                                  [Page 15]
  843.  
  844. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  845.  
  846.  
  847.    The lists of child and leaf interfaces can be implemented as bitmaps.
  848.  
  849. 5.1 Sending Routing Messages
  850.  
  851.    DVMRP routing messages can be used for three basic purposes: to
  852.    periodically supply all routing information, to gratuitously supply
  853.    routing information for recently changed routes, or supply some or
  854.    all routes in response to a request.
  855.  
  856.    Routing messages sent to physical interfaces should have an IP TTL of
  857.    1.
  858.  
  859.    A number of timeouts and rates are used by the routing and forwarding
  860.    algorithms.  See section 6 for their values.
  861.  
  862.    Rules for when to send routing messages:
  863.  
  864.       - Every FULL_UPDATE_RATE seconds a router should send out
  865.         DVMRP messages with all of its routing information to all of its
  866.         virtual interfaces.  To prevent routers from synchronizing when
  867.         they send updates, a real-time timer must be used.
  868.  
  869.       - Whenever a route is changed, a routing update should be sent
  870.         for that route.  Some delay must occur between triggered
  871.         updates to avoid flooding the network with triggered updates;
  872.         intervals of TRIGGERED_UPDATE_RATE seconds is suggested.
  873.  
  874.       - A request for all routes should be sent on all virtual
  875.         interfaces when an DVMRP router is restarted.
  876.  
  877.       - If possible, when a DVMRP router is about to terminate
  878.         execution, it should send out DVMRP messages with metrics
  879.         equal to infinity for all of its routes, on all virtual
  880.         interfaces.
  881.  
  882.    When sending to routers connected via networks that support
  883.    multicasting, the messages should be multicast to address 224.0.0.4.
  884.    Therefore, routers must listen to multicast address 224.0.0.4 on
  885.    every physical interface that supports multicasting.  If multicasting
  886.    isn't supported, broadcasting can be used.  As already mentioned,
  887.    routing updates to tunnels should be sent as unicast datagrams to the
  888.    remote end-point of the tunnel.
  889.  
  890.    When sending routing messages, except in response to a specific route
  891.    request (via RDA command with a non-zero count), poisoned split
  892.    horizon processing must be done.  This means that given a route that
  893.    uses network X, routing updates sent to network X must include that
  894.    route with the metric equal to the infinity and should include the
  895.  
  896.  
  897.  
  898. Waitzman, Partridge & Deering                                  [Page 16]
  899.  
  900. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  901.  
  902.  
  903.    appropriate flag set in a FLAGS0 command.
  904.  
  905.    Poisoned split horizon is one way to reduce the likelihood of routing
  906.    loops.  Another method, not available in RIP, is to choose a better
  907.    infinity in a route.  For routes propagated in a small, but well
  908.    connected, network an infinity smaller than 16 might be better.  The
  909.    smaller the infinity, the less time a counting-to-infinity event will
  910.    take.  In traversing a wide internet, an infinity of 16 might be too
  911.    small.  At the cost of a longer counting-to-infinity event, the
  912.    infinity can be increased.
  913.  
  914.    One concept in Internet Multicasting is to use "thresholds" to
  915.    restrict which multicast datagrams exit a network.  Multicast routers
  916.    on the edge of a subnetted network or autonomous system may require a
  917.    datagram to have large TTL to exit a network.  This mechanism keeps
  918.    most multicast datagrams within the network, reducing external
  919.    traffic.  An application that wants to multicast outside of its
  920.    network would need to give its multicast datagrams at least a TTL of
  921.    the sum of the threshold and the distance to the edge of the network
  922.    (assuming TTL is used as a hop count within the network).  A
  923.    configuration option should allow specifying the threshold for both
  924.    physical interfaces and tunnels.
  925.  
  926.    When a router is started, it must send out a request for all routes
  927.    on each of its virtual interfaces.  The request is a message that has
  928.    an RDA command with a count equal to 0 in it.
  929.  
  930. 5.2 Receiving Routing Messages
  931.  
  932.    A router must know the virtual interface that a routing message
  933.    arrived on.  Because the routing message may be addressed to the
  934.    all-multicast-routers IP address, and because of tunnels, the
  935.    incoming interface can not be identified merely by examining the
  936.    message's IP destination address
  937.  
  938.    For each route expressed in a routing message, the following must
  939.    occur:
  940.  
  941.    IF a metric was given for the route:
  942.    THEN    add in the metric of the virtual interface that the message
  943.            arrived on.
  944.  
  945.    Lookup the route's destination address in the routing tables.
  946.  
  947.    IF the route doesn't exist in the tables:
  948.    THEN    try to find a route to the same network in the routing
  949.            tables.
  950.            IF that route exists in the tables:
  951.  
  952.  
  953.  
  954. Waitzman, Partridge & Deering                                  [Page 17]
  955.  
  956. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  957.  
  958.  
  959.            THEN    IF this route came from the same router as the router
  960.                    that the found route came from:
  961.                    THEN    CONTINUE with next route.
  962.            IF route doesn't have a metric of infinity:
  963.                    THEN    add the route to the routing tables.
  964.            CONTINUE with next route.
  965.  
  966.    IF this route came from the same router as the router that the found
  967.       route came from:
  968.    THEN    clear the route timer.
  969.            IF a metric was received, and it is different than the found
  970.            route's metric:
  971.            THEN    change the found route to use the new metric and
  972.                    infinity.
  973.                    IF the metric is equal to the infinity:
  974.                    THEN    set the route timer to the
  975.                            EXPIRATION_TIMEOUT.
  976.                    CONTINUE with next route.
  977.            IF the received infinity does not equal the found route's
  978.            infinity:
  979.            THEN    change the found route's infinity to be the received
  980.                    infinity.
  981.                    change the found route's metric to be the minimum of
  982.                    the received infinity and the found route's metric.
  983.    ELSE    IF a metric was received, and (it is less than the found
  984.            route's metric or (the route timer is at least halfway to the
  985.            EXPIRATION_TIMEOUT and the found route's metric equals the
  986.            received metric, and the metric is less than the received
  987.            infinity)):
  988.            THEN    change the routing tables to use the received route.
  989.                    clear the route timer.
  990.    CONTINUE with next route.
  991.  
  992. 5.3 Neighbors
  993.  
  994.    A list should be kept of the neighboring multicast routers on every
  995.    attached network.  The information can be derived by the DVMRP
  996.    routing messages that are received.  A neighbor that has not been
  997.    heard from in NEIGHBOR_TIMEOUT seconds should be considered to be
  998.    down.
  999.  
  1000. 5.4 Local Group Memberships
  1001.  
  1002.    As required by [2], a multicast router must keep track of group
  1003.    memberships on the multicast-capable networks attached to it.  Every
  1004.    QUERY_RATE seconds an IGMP membership request should be sent to the
  1005.    All Hosts multicast address (224.0.0.1) on each network by a
  1006.    designated router on that network.  The IGMP membership request will
  1007.  
  1008.  
  1009.  
  1010. Waitzman, Partridge & Deering                                  [Page 18]
  1011.  
  1012. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  1013.  
  1014.  
  1015.    cause hosts to respond with IGMP membership reports after a small
  1016.    delay.  Hosts will send the report for a group to the group's
  1017.    multicast address.
  1018.  
  1019.    The membership requests should have an IP TTL of 1.
  1020.  
  1021.    The routers on a network elect or "designate" a single router to do
  1022.    the queries.  The designated router is the router with the lowest IP
  1023.    address on that network.  Upon startup a router considers itself to
  1024.    be the designated router until it learns (presumably through routing
  1025.    messages) of a router with a lower address.  To learn about the group
  1026.    members present on a network at startup, a router should multicast a
  1027.    number of membership requests, separated by a small delay.  We
  1028.    suggest sending three requests separated by four seconds.
  1029.  
  1030.    The multicast router must receive all datagrams sent to all multicast
  1031.    addresses.  Upon receiving an IGMP membership report for a group from
  1032.    an interface, it must either record the existence of that group on
  1033.    the interface and record the time, or update the time if the group is
  1034.    already recorded.  The recorded group memberships must be timed-out.
  1035.    If a group member report is not received for a recorded group after
  1036.    MEMBERSHIP_TIMEOUT seconds, the recorded group should be deleted.
  1037.  
  1038. 6. Forwarding Algorithm
  1039.  
  1040.    The section describes the multicast forwarding algorithm and the
  1041.    state that must be kept for the algorithm.
  1042.  
  1043.    The forwarding algorithm is applied to determine how multicast
  1044.    datagrams arriving on a physical interface or a tunnel should be
  1045.    handled.  If multicast datagrams were flooded, a datagram received on
  1046.    one virtual interface would be forwarded out of every other virtual
  1047.    interface.  Because of redundant paths in the internet, datagrams
  1048.    would be duplicated.  The child and leaf information, that the
  1049.    routing algorithm supplies, is used to prune branches in the tree to
  1050.    all possible destinations.
  1051.  
  1052.    In route entries, there is a dominant router address for each virtual
  1053.    interface.  This address is the address of some router that has a
  1054.    route with a lower metric (and whose metric does not equal infinity)
  1055.    to the destination, on that virtual interface.  The dominant router
  1056.    address is not set for the next-hop virtual interface.
  1057.  
  1058.    Also in route entries, there is a subordinate router address for each
  1059.    virtual interface.  This address is the address of some router that
  1060.    considers this router to be the parent of the virtual network.
  1061.    Therefore, the subordinate router address is not set for a virtual
  1062.    interface to a leaf network.
  1063.  
  1064.  
  1065.  
  1066. Waitzman, Partridge & Deering                                  [Page 19]
  1067.  
  1068. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  1069.  
  1070.  
  1071.    The algorithm for manipulating the children and leaf lists in route
  1072.    entries is:
  1073.  
  1074.    Upon router startup:
  1075.            Create a route entry for each virtual interface, with:
  1076.                - all other virtual interfaces in its child list,
  1077.                - an empty leaf list,
  1078.                - no dominant router addresses, and
  1079.                - no subordinate router addresses.
  1080.            Start a hold down timer for each virtual interface, with
  1081.            a value of LEAF_TIMEOUT.
  1082.  
  1083.    Upon receiving a new route:
  1084.            Create the route entry, with:
  1085.                - all virtual interfaces, other than the one on which the
  1086.                  new route was received, in its child list,
  1087.                - empty leaf list,
  1088.                - no dominant router addresses, and
  1089.                - no subordinate router addresses.
  1090.            Start the hold down timer for all virtual interfaces, other
  1091.            than the one on which the new route was received, with a
  1092.            value of LEAF_TIMEOUT.
  1093.  
  1094.    Upon receiving a route on virtual interface V from neighbor N with a
  1095.    lower metric than the one in the routing table (or the same metric as
  1096.    the one in the routing table, if N's address is less than my address
  1097.    for V), for that route:
  1098.      If V is in the child list, delete V from the child list.
  1099.      If there is no dominant router for V and if V is not (now) the
  1100.      next-hop virtual interface, record N as the dominant router.
  1101.  
  1102.    Upon receiving a route on virtual interface V from neighbor N with a
  1103.    larger metric than the one in the routing table (or the same metric
  1104.    as the one in the routing table, if N's address is greater than my
  1105.    address for V), for that route:
  1106.      If N is the dominant router for V, delete N as the dominant router
  1107.      and add V to the child list.
  1108.  
  1109.    Upon receiving a route from neighbor N on virtual interface V with a
  1110.    metric equal to infinity (the split horizon flag should also be set),
  1111.    for that route:
  1112.      If V is in the leaf list, delete V from the leaf list.
  1113.      If there is no subordinate router for V, record N as the
  1114.      subordinate router.
  1115.  
  1116.    Upon receiving a route from neighbor N on virtual interface V with a
  1117.    metric other than infinity (and no split horizon flag), for that
  1118.    route:
  1119.  
  1120.  
  1121.  
  1122. Waitzman, Partridge & Deering                                  [Page 20]
  1123.  
  1124. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  1125.  
  1126.  
  1127.      If N is the subordinate router for V, delete N as the subordinate
  1128.      router and start the hold down timer for V.
  1129.  
  1130.    Upon timer expiration for a virtual interface (V), for each route:
  1131.      If there is no subordinate router for V, add V to the leaf list.
  1132.  
  1133.    Upon failure of neighbor N on virtual interface V, for each route:
  1134.      If N is the dominant router for V, delete N as the dominant router
  1135.      and add V to the child list.
  1136.      If N is the subordinate router for V, delete N as the subordinate
  1137.      router and start the hold down timer for V.
  1138.  
  1139.    The forwarding algorithm is:
  1140.  
  1141.    IF the IP TTL is less than 2:
  1142.    THEN    CONTINUE with next datagram.
  1143.  
  1144.    find the route to the source of the IP datagram.
  1145.  
  1146.    IF no route exists:
  1147.    THEN    CONTINUE with next datagram.
  1148.  
  1149.    IF the datagram was not received on the next-hop virtual interface
  1150.    for the route:
  1151.    THEN    CONTINUE with next datagram.
  1152.  
  1153.    IF the datagram is tunneled:
  1154.    THEN    replace the datagram's source address with the first address
  1155.            in the IP loose source route.
  1156.            replace the datagram's destination address with the second
  1157.            address in the IP loose source route.
  1158.            delete the loose source route and the null option from the
  1159.            datagram and adjust the IP header length fields to reflect
  1160.            the deletion.
  1161.  
  1162.    If the datagram destination is group 224.0.0.0 or group 224.0.0.1:
  1163.    THEN    CONTINUE with next datagram.
  1164.  
  1165.    FOR each virtual interface V
  1166.    DO      IF V is in the child list for the source of the datagram:
  1167.            THEN    IF V is not in the leaf list for the source
  1168.                    OR there are members of the destination group on V:
  1169.                    THEN    IF the IP TTL is greater then V's threshold:
  1170.                            THEN    subtract 1 from the IP TTL
  1171.                                    forward the datagram out V
  1172.  
  1173.  
  1174.  
  1175.  
  1176.  
  1177.  
  1178. Waitzman, Partridge & Deering                                  [Page 21]
  1179.  
  1180. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  1181.  
  1182.  
  1183. 7. Time Values
  1184.  
  1185.    This section contains a list of the various rates and timeouts, their
  1186.    meanings, and their values.  All values are in seconds.
  1187.  
  1188.    How dynamic the routing environment is effects the following rates.
  1189.    A lower rate will allow quicker adaptation to a change in the
  1190.    environment, at the cost of wasting network bandwidth.
  1191.  
  1192.    FULL_UPDATE_RATE = 60
  1193.            - How often routing messages containing complete routing
  1194.              tables are sent.
  1195.  
  1196.    TRIGGERED_UPDATE_RATE = 5
  1197.            - How often triggered routing messages may be sent out.
  1198.  
  1199.    Raising the following rates and timeouts may increase the time that
  1200.    packets may be forwarded to a virtual interface unnecessarily.
  1201.  
  1202.    QUERY_RATE = 120
  1203.            - How often local group membership is queried.
  1204.  
  1205.    MEMBERSHIP_TIMEOUT = 2 * QUERY_RATE + 20
  1206.            - How long a local group membership is valid without
  1207.              confirmation.
  1208.  
  1209.    LEAF_TIMEOUT = 2 * FULL_UPDATE_RATE + 5
  1210.            - How long the hold down timer is for a virtual interface.
  1211.  
  1212.    Increasing the following timeouts will increase the stability of the
  1213.    routing algorithm, at the cost of slower reactions to changes in the
  1214.    routing environment.
  1215.  
  1216.    NEIGHBOR_TIMEOUT = 4 * FULL_UPDATE_RATE
  1217.            - How long a neighbor is considered up without confirmation.
  1218.              This is important for timing out routes, and for setting
  1219.              the children and leaf flags.
  1220.  
  1221.    EXPIRATION_TIMEOUT = 2 * FULL_UPDATE_RATE
  1222.            - How long a route is considered valid without confirmation.
  1223.              When this timeout expires, packets will no longer be
  1224.              forwarded on the route, and routing updates will consider
  1225.              this route to have a metric of infinity.
  1226.  
  1227.    GARBAGE_TIMEOUT = 4 * FULL_UPDATE_RATE
  1228.            - How long a route exists without confirmation.  When this
  1229.              timeout expires, routing updates will no longer contain any
  1230.              information on this route, and the route will be deleted.
  1231.  
  1232.  
  1233.  
  1234. Waitzman, Partridge & Deering                                  [Page 22]
  1235.  
  1236. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  1237.  
  1238.  
  1239. 8. Configuration options
  1240.  
  1241.    A router should be configurabled with the following information:
  1242.  
  1243.    - Tunnel descriptions: local end-point, remote end-point, metric, and
  1244.      threshold.  If no threshold is provided, the metric should be used
  1245.      as the default threshold.
  1246.  
  1247.    - For a physical interface: metric, infinity, threshold and
  1248.      subnetwork mask.  If no threshold is provided, the metric should be
  1249.      used as the default threshold.
  1250.  
  1251. 9. Conclusion
  1252.  
  1253.    This memo has presented DVMRP, an extensible distance-vector-style
  1254.    routing protocol, and a TRPB routing algorithm.  An implementation of
  1255.    the ideas presented in this document has been done, and is being
  1256.    tested.
  1257.  
  1258.    The added features in DVMRP, as compared to RIP, give it flexibility
  1259.    at the cost of more complex processing.  DVMRP still has the
  1260.    disadvantages of being a distance-vector algorithm.  Because link-
  1261.    state algorithms maintain much of the state information that DVMRP
  1262.    has to maintain in excess of what RIP needs, a multicast link-state
  1263.    routing protocol should be developed.
  1264.  
  1265.    The TRPB algorithm can cause unneeded datagrams to be sent.  The
  1266.    Reverse Path Multicasting algorithm (RPM) [3] might be a better
  1267.    algorithm.  The NMR and NMR-cancel DVMRP messages are designed to
  1268.    support RPM.  Further research is needed on this topic.
  1269.  
  1270. 10. Acknowledgements
  1271.  
  1272.    We would like to thank Robb Foster, Alan Dahlbom, Ross Callon, and
  1273.    the IETF Host Working Group for their ideas.
  1274.  
  1275. 11. Bibliography
  1276.  
  1277.      [1]  Hedrick, C., "Routing Information Protocol", RFC 1058, Rutgers
  1278.           University, June 1988.
  1279.  
  1280.      [2]  Deering, S., "Host Extensions for IP Multicasting", RFC 1054,
  1281.           Stanford University, May 1988.
  1282.  
  1283.      [3]  Deering, S., "Multicast Routing in Internetworks and Extended
  1284.           LANs", SIGCOMM Summer 1988 Proceedings, August 1988.
  1285.  
  1286.      [4]  Callon, R., "A Comparison of 'Link State' and 'Distance
  1287.  
  1288.  
  1289.  
  1290. Waitzman, Partridge & Deering                                  [Page 23]
  1291.  
  1292. RFC 1075       Distance Vector Multicast Routing Protocol  November 1988
  1293.  
  1294.  
  1295.           Vector' Routing Algorithms", DEC, November 1987.
  1296.  
  1297.      [5]  Postel, J., "Internet Protocol", RFC 791, USC/Information
  1298.           Sciences Institute, September 1981.
  1299.  
  1300.      [6]  Mills, D., "Toward an Internet Standard Scheme for
  1301.           Subnetting", RFC 940, University of Delaware, April 1985.
  1302.  
  1303.  
  1304.  
  1305.  
  1306.  
  1307.  
  1308.  
  1309.  
  1310.  
  1311.  
  1312.  
  1313.  
  1314.  
  1315.  
  1316.  
  1317.  
  1318.  
  1319.  
  1320.  
  1321.  
  1322.  
  1323.  
  1324.  
  1325.  
  1326.  
  1327.  
  1328.  
  1329.  
  1330.  
  1331.  
  1332.  
  1333.  
  1334.  
  1335.  
  1336.  
  1337.  
  1338.  
  1339.  
  1340.  
  1341.  
  1342.  
  1343.  
  1344.  
  1345.  
  1346. Waitzman, Partridge & Deering                                  [Page 24]
  1347.